class Solution {
public:
    bool dfs(TreeNode *left, TreeNode *right) {
        if (left == nullptr && right == nullptr) return true;
        if (left == nullptr || right == nullptr) return false;
        return left->val == right->val && dfs(left->left, right->right) && dfs(left->right, right->left);
    }

    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return dfs(root->left, root->right);
    }

    bool isSymmetric_2(TreeNode* root) {
        if (!root) return root;
        //可以简化为一个栈
        queue<TreeNode *> lq;
        queue<TreeNode *> rq;
        lq.push(root->left);
        rq.push(root->right);
        while (!lq.empty() && !rq.empty()) {           
            int size = lq.size();
            for (int i = 0; i < size; ++i) {
                TreeNode *lnode = lq.front(); lq.pop();
                TreeNode *rnode = rq.front(); rq.pop();
                if (!lnode && !rnode) continue;
                else if (!lnode || !rnode) return false;
                else {
                    if (lnode->val == rnode->val) {
                        lq.push(lnode->left);
                        lq.push(lnode->right);
                        rq.push(rnode->right);
                        rq.push(rnode->left);
                    } else {
                        return false;
                    }
                }
            }  
        }
        return true;
    }
};